#include <vector>

using std::vector;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> vp;
        vector<TreeNode*> vq;
        bool findP = false;
        bool findQ = false;
        find(root, vp, vq, p, q, findP, findQ);
        int index = 0;
        int common = std::min(vp.size(), vq.size());
        while (index < common) {
            if (vp[index]->val == vq[index]->val) {
                index++;
            }
            else {
                break;
            }
        }
        return vp.size() > vq.size() ? vp[index - 1] : vq[index - 1];
    }

    void find(TreeNode* node, vector<TreeNode*>& vp, vector<TreeNode*>& vq, TreeNode* p, TreeNode* q, bool& findP, bool& findQ) {
        if (node->val == p->val) {
            vp.push_back(node);
            findP = true;
        }
        else if (node->val == q->val) {
            vq.push_back(node);
            findQ = true;
        }
        if (!findP || !findQ) {
            if (node->left != nullptr) {
                if (!findP) {
                    vp.push_back(node);
                }
                if (!findQ) {
                    vq.push_back(node);
                }
                find(node->left, vp, vq, p, q, findP, findQ);
                if (!findP) {
                    vp.pop_back();
                }
                if (!findQ) {
                    vq.pop_back();
                }
            }
        }
        if (!findP || !findQ) {
            if (node->right != nullptr) {
                if (!findP) {
                    vp.push_back(node);
                }
                if (!findQ) {
                    vq.push_back(node);
                }
                find(node->right, vp, vq, p, q, findP, findQ);
                if (!findP) {
                    vp.pop_back();
                }
                if (!findQ) {
                    vq.pop_back();
                }
            }
        }
    }
};